#include "util.h"
#include "buffer_trans.h"
#include "hashdb.h"
uint32 hash1(uchar *key,int len){
    uchar *nkey=key;
	uchar *it;
	uint32 h;
#define PRIME1		37
	for (it= nkey, h = 0; len--;)
		h = h * PRIME1 ^ (*it++ - ' ');
	return h;
}
#define HASH2(hv) ((hv)&65535)
struct cache* cachenew(int fd,int nbucket,int pagesiz,int maxbytes,int swapratio){
    struct cache *cc=calloc(1,sizeof(struct cache));
	int pshift=pagesiz>0?lg2(pagesiz):DEF_CACHE_PSHIFT;
	cc->pgsiz=1<<pshift;
	cc->npg=0;
	cc->fd=fd;
	cc->swapratio=swapratio>0?swapratio:DEF_CACHE_SWAPRATIO;
	int mb=maxbytes>0?maxbytes:DEF_CACHE_MAXBYTES;
	cc->maxpgs=(mb+cc->pgsiz-1)>>pshift;
	cc->nbucket=nbucket>0?nbucket:DEF_CACHE_BUCKETS;
	cc->buckets=calloc(cc->nbucket,sizeof(struct cnode*));
	pthread_rwlock_init(&cc->lock,NULL);
	DEBUG(printf("%s:fd=%d nbucket=%d pgsiz=%d maxpgs=%d\n",__func__,cc->fd,cc->nbucket,cc->pgsiz,cc->maxpgs));
	return cc;
}
#define HEADREMOVE(head,n)  do{\
                               (head)->next->pre=NULL;\
                               (n)=(head);\
							   (head)=(head)->next;\
							   (n)->next=NULL;\
						    }while(0)
#define TAILREMOVE(tail,n)  do{\
                                (n)=(tail);\
								(tail)=(tail)->pre;\
								(tail)->next=NULL;\
								(n)->pre=NULL;\
                            }while(0)
#define HEADINSERT(head,n)  do{\
                               (n)->next=(head);\
							   (head)->pre=(n);\
							   (n)->pre=NULL;\
							   (head)=(n);\
                            }while(0)
#define TAILINSERT(tail,n)  do{\
                                (tail)->next=(n);\
								(n)->pre=(tail);\
								(n)->next=NULL;\
								(tail)=(n);\
                            }while(0)
struct cnode* getfreenode(struct cache *cc){
    struct cnode *nd=NULL;
	if(cc->flast!=NULL){
	    DEBUG(printf("enough room\n"));
		if(cc->flast!=cc->ffirst)
		    TAILREMOVE(cc->flast,nd);
		else{
		    nd=cc->flast;
			cc->flast=cc->ffirst=NULL;
		}
		if(!(nd->haf&F_DELETE)){
		    uint32 hv1=hash1((uchar*)&nd->pgno,sizeof(uint64));
			cremove(cc,nd,hv1);
		}
	}
	else if(TRANSACTION_IN(cc)||cc->npg<cc->maxpgs){
	    nd=malloc(sizeof(struct cnode)+cc->pgsiz);
		DEBUG(printf("%s:crate a new node\n",__func__);)
		cc->npg++;
	}
	else{
	    DEBUG(printf("swap node\n"));
		//gettimeofday(&b,NULL);
	    swapnode(cc);
		//gettimeofday(&e,NULL);
		//cc->cmptime+=e.tv_sec-b.tv_sec+(e.tv_usec-b.tv_usec)/1000000.0;
		if(cc->flast==NULL){
		    nd=malloc(sizeof(struct cnode)+cc->pgsiz);
			cc->npg++;
		}else{
		    DEBUG(printf("%s:cc->flast->pgno=%d\n",__func__,cc->flast->pgno);)
		    if(cc->flast!=cc->ffirst)
		        TAILREMOVE(cc->flast,nd);
			else{
			    nd=cc->flast;
			    cc->flast=cc->ffirst=NULL;
			}
			if(!(nd->haf&F_DELETE)){
		        uint32 hv1=hash1((uchar*)&nd->pgno,sizeof(uint64));
			    //hv1=hv1%cc->nbucket;
			    //pthread_rwlock_wrlock(&cc->bmtx[hv]);
			    cremove(cc,nd,hv1);
			    //pthread_rwlock_unlock(&cc->btmx[hv]);
		    }
		}
		
	}
	//pthread_mutex_unlock(&cc->fp_lock);
	return nd;
}
char* addpage(struct cache *cc,uint64 pgno,char *pg,uint32 flag){
	struct cnode *nd=NULL;
	uint32 hv1=hash1((uchar*)&pgno,sizeof(uint64));
	uint16 hv2=HASH2(hv1);
	//printf("%s:add page pgno=%d flag=%x\n",__func__,pgno,flag);
	//pthread_rwlock_wrlock(&cc->bmtx[hv1]);
	//pthread_mutex_lock(&cc->lru_lock);
	if(!TRANSACTION_IN(cc)&&pthread_rwlock_wrlock(&cc->lock)!=0){
	    printf("%s:lock cache error\n",__func__);
		exit(1);
	}
	if((nd=getfreenode(cc))==NULL){
	    printf("%s:get node fail\n",__func__); 
		exit(1);
	}
	memcpy((char*)nd+sizeof(struct cnode),pg,cc->pgsiz);
	addnode(cc,hv1%cc->nbucket,hv2,pgno,nd,flag);
	//pthread_mutex_unlock(&cc->lru_lock);
	//pthread_rwlock_unlock(&cc->bmtx[hv1]);
	if(!TRANSACTION_IN(cc)&&pthread_rwlock_unlock(&cc->lock)!=0){
	    printf("%s:unlock cache fail\n",__func__);
		exit(1);
	}
	return (char*)nd+sizeof(struct cnode);
}
int swapnode(struct cache* cc){
    if(cc==NULL||cc->npg<cc->maxpgs) return true;
	//cc->swaptimes++;
	int npg=cc->npg>cc->maxpgs?cc->npg-cc->maxpgs+cc->maxpgs/cc->swapratio:cc->npg/cc->swapratio;
	if(npg==0) npg=1;
	struct cnode *it=cc->last;
	int nrem=0;
	//printf("%s:going to swap %d pg\n",__func__,npg);
	struct cnode *tn;
	struct timeval beg,end;
	
	while(npg>nrem&&it!=NULL){
	    //printf("%s:swap pgno=%d\n",__func__,it->pgno);
	    if((it->haf&F_WRITE)||(it->haf&F_READ)){
		    //printf("%s:pgno=%d flag=%x\n",__func__,it->pgno,it->haf&CN_FMASK);
		    it=it->pre;
		    continue;
		}else if(it->haf&F_DIRTY){
			//gettimeofday(&beg,NULL);
		        seekwrite(cc->fd,(char*)it+sizeof(struct cnode),cc->pgsiz,it->pgno);
				/*if(fseek(cc->fp,it->pgno,SEEK_SET)<0){
				    printf("%s:seek error:pgno=%d:%s\n",__func__,it->pgno,strerror(errno));
					exit(1);
				}
				//int ret;
				if(fwrite((char*)it+sizeof(struct cnode),cc->pgsiz,1,cc->fp)!=1){
				    printf("%s:wirte error:%s:pgno=%d\n",__func__,strerror(errno),it->pgno);
					exit(1);
				}else{
				    struct leaf *l=(struct leaf*)((char*)it+sizeof(struct cnode));
				    printf("%s:inum=%d write pgno=%d ok\n",__func__,(l->lower-LEAFIDXBEG)/sizeof(int16),it->pgno);
					fflush(cc->fp);
					fsync(fileno(cc->fp));
					if(fseek(cc->fp,it->pgno,SEEK_SET)<0){
					    printf("%s:seek error:%s\n",__func__,strerror(errno));
					}
					if(fread((char*)it+sizeof(struct cnode),cc->pgsiz,1,cc->fp)==1){
					    l=(struct leaf*)((char*)it+sizeof(struct cnode));
					    printf("%s:fread inum=%d pgno=%d\n",__func__,(l->lower-LEAFIDXBEG)/sizeof(int16),it->pgno);
					}
					if(lseek(fileno(cc->fp),it->pgno,SEEK_SET)<0){
					    printf("%s:lseek error:%s\n",__func__,strerror(errno));
					}
					if(read(fileno(cc->fp),(char*)it+sizeof(struct cnode),cc->pgsiz)!=cc->pgsiz){
					    printf("%s:read error:%s\n",__func__,strerror(errno));
					}else{
					    l=(struct leaf*)((char*)it+sizeof(struct cnode));
					    printf("%s:read inum=%d\n",__func__,(l->lower-LEAFIDXBEG)/sizeof(int16));
					}
				}
				if(it->pgno==1230336){
				    fflush(cc->fp);
				    char buf[512];
					struct leaf *l=(struct leaf*)((char*)it+sizeof(struct cnode));
					printf("%s:pgno=%d inum=%d\n",__func__,it->pgno,(l->lower-LEAFIDXBEG)/sizeof(int16));
					if(fseek(cc->fp,it->pgno,SEEK_SET)<0){
					    printf("seek error\n");
						exit(1);
					}
					if(fread(buf,512,1,cc->fp)!=1){
					    printf("read error:%s\n",strerror(errno));
						exit(1);
					}
					l=(struct leaf*)buf;
	                printf("pgno=%d inum=%d\n",it->pgno,(l->lower-LEAFIDXBEG)/sizeof(int16));
					exit(1);
				}*/
			//gettimeofday(&end,NULL);
	        //cc->swaptime+=end.tv_sec-beg.tv_sec+(end.tv_usec-beg.tv_usec)/1000000.0;
			//else writen(cc->fd,(char*)it+sizeof(struct cnode),cc->pgsiz);
			//cc->lastoffset=it->pgno+cc->pgsiz;
			it->haf&=~CN_FMASK;
			//cc->writenum++;
		}
		if(it->pre!=NULL)
		    it->pre->next=it->next;
		else
		    cc->first=it->next;
		if(it->next!=NULL)
		    it->next->pre=it->pre;
		else cc->last=it->pre;
		//printf("%s:remove pgno=%d\n",__func__,it->pgno);
		//cremove(cc,it);
		if(cc->npg>cc->maxpgs){
		    tn=it;
			it=it->pre;
		    free(tn);
			cc->npg--;
		}else{
		    tn=it->pre;
		    if(cc->ffirst!=NULL)
		        HEADINSERT(cc->ffirst,it);
		    else{
			    cc->ffirst=it;
				cc->flast=it;
				it->next=it->pre=NULL;
			}
			it->haf|=F_FREE;
			it=tn;
		}
		nrem++;
	}
	//fflush(cc->fp);
	//fsync(fileno(cc->fp));
	cc->swapnum+=nrem;
	DEBUG(printf("%s:swap %d pgs\n",__func__,nrem));
	return nrem;
}
int cremove(struct cache *cc,struct cnode *nd,uint32 hv1){
	uint16 hv2=HASH2(hv1),nhv;
	hv1=hv1%cc->nbucket;
	struct cnode *pn=cc->buckets[hv1];
	struct cnode *qn=pn;
	if(nd->haf&F_DELETE){
	    DEBUG(printf("%s:pgno=%d already deleted\n",__func__,nd->pgno));
		return false;
	}
	while(qn!=NULL){
	    nhv=qn->haf&CN_HMASK;
	    if(nhv==hv2){
		    if(qn->pgno==nd->pgno) break;
			else if(qn->pgno>nd->pgno){
			    pn=qn;
				qn=qn->left;
			}else{
			    pn=qn;
				qn=qn->right;
			}
		}
		else if(nhv>hv2){
		    pn=qn;
			qn=qn->left;
		}else{
		    pn=qn;
			qn=qn->right;
		}
		//printf("%s:pn->pgno=%d\n",__func__,pn->pgno);
	}
	if(qn==NULL){
	    printf("%s:locate the node pgno=%u fail\n",__func__,nd->pgno);
		struct cnode *t=cc->first;
		printf("%s:lru seq\n",__func__);
		while(t!=NULL){
		    printf("%s:pgno=%d\n",__func__,t->pgno);
			t=t->next;
		}
		printf("%s:free seq\n",__func__);
		t=cc->ffirst;
		while(t!=NULL){
		    printf("%s:pgno=%d\n",__func__,t->pgno);
			t=t->next;
		}
		int i;
		for(i=0;i<cc->nbucket;i++){
		    printf("%s:traver hashbucket%d\n",__func__,i);
			traverse(cc,i);
		}
		exit(1);
		return false;
	}
	else if(qn->left==NULL){
	    if(pn==qn) cc->buckets[hv1]=qn->right; 
	    else if(pn->left==qn) pn->left=qn->right;
		else pn->right=qn->right;
	}
	else if(qn->right==NULL){
	    if(pn==qn) cc->buckets[hv1]=qn->left;
	    else if(pn->left==qn) pn->left=qn->left;
	    else pn->right=qn->left;
	}
	else{
	    struct cnode *lnp=qn->left;
		struct cnode *ln=lnp;
		while(ln->right!=NULL){
		    lnp=ln;
			ln=ln->right;
		}
		if(pn==qn) cc->buckets[hv1]=ln;
		else if(pn->left==qn) pn->left=ln;
		else pn->right=ln;
		if(ln!=lnp){
		    lnp->right=ln->left;
		    ln->left=qn->left;
		}
		ln->right=qn->right;
	}
	nd->haf=F_DELETE;
	return true;
}
int traverse(struct cache *cc,int root){
    struct cnode *stack[100];
	int tail=0,head=0;
	if(cc->buckets[root]==NULL){
	    printf("%s:no child\n",__func__);
		return true;
	}
	stack[head++]=cc->buckets[root];
	while(tail!=head){
	    struct cnode *nd=stack[tail++];
	    printf("%s:pgno=%d hash=%x\n",__func__,nd->pgno,nd->haf&CN_HMASK);
		if(nd->right!=NULL) stack[head++]=nd->right;
		if(nd->left!=NULL) stack[head++]=nd->left;
		if(head>=100)exit(1);
	}
	return true;
}
char *getpage(struct cache *cc,uint64 pgno,uint32 flag){
	uint32 hv1=hash1((uchar*)&pgno,sizeof(uint64));
	uint16 hv2=HASH2(hv1),nhv;
	hv1=hv1%cc->nbucket;
	if(!TRANSACTION_IN(cc)&&pthread_rwlock_wrlock(&cc->lock)!=0){
	    printf("%s:lock fail\n",__func__);
		exit(1);
	}
	struct cnode *nd=cc->buckets[hv1];
	//printf("%s:pgno=%d\n",__func__,pgno);
	while(nd!=NULL){
	    nhv=nd->haf&CN_HMASK;
	    if(hv2==nhv){
		    if(nd->pgno==pgno){
			    if(nd->haf&F_FREE){
					if(nd->pre!=NULL) nd->pre->next=nd->next;
					else cc->ffirst=nd->next;
					if(nd->next!=NULL) nd->next->pre=nd->pre;
					else cc->flast=nd->pre;
				    if(cc->first==NULL){
					    cc->first=cc->last=nd;
						nd->next=nd->pre=NULL;
					}else
					    HEADINSERT(cc->first,nd);
					nd->haf&=~F_FREE;
				}
		        else if(nd!=cc->first){
			        nd->pre->next=nd->next;
				    if(nd->next!=NULL) nd->next->pre=nd->pre;
				    else cc->last=nd->pre;
				    HEADINSERT(cc->first,nd);
			    }
			    nd->haf|=flag&CN_FMASK;
				if(!TRANSACTION_IN(cc)&&pthread_rwlock_unlock(&cc->lock)!=0){
				    printf("%s:unlock fail\n",__func__);
					exit(1);
				}
		        return (char*)nd+sizeof(struct cnode);
		    }else if(nd->pgno>pgno) nd=nd->left;
			else nd=nd->right;
		}
		else if(nhv>hv2)
		    nd=nd->left;
		else nd=nd->right;
	}
	//printf("%s:create a new node:pgno=%d flag=%x\n",__func__,pgno,flag);
	struct cnode *nnd=NULL;
	nnd=getfreenode(cc);
	seekread(cc->fd,(char*)nnd+sizeof(struct cnode),cc->pgsiz,pgno);
	addnode(cc,hv1,hv2,pgno,nnd,flag);
	if(!TRANSACTION_IN(cc)&&pthread_rwlock_unlock(&cc->lock)!=0){
	    printf("%s:unlock fail\n",__func__);
		exit(1);
	}
	return (char*)nnd+sizeof(struct cnode);
}
int putpage(struct cache *cc,char *page,uint32 flag){
    struct cnode *nd=(struct cnode*)(page-sizeof(struct cnode));
	uint32 oflag=(nd->haf&(~F_READ)&(~F_WRITE))|(flag&CN_FMASK);
	nd->haf=(oflag&CN_FMASK)|(nd->haf&CN_HMASK);
	//printf("%s:pgno=%d flag=%x\n",__func__,nd->pgno,nd->haf);
	return true;
}
int addnode(struct cache *cc,uint32 hv1,uint16 hv2,uint64 pgno,struct cnode *nd,uint32 flag){
	struct cnode *n=cc->buckets[hv1];
	struct cnode *pn=cc->buckets[hv1];
	uint16 nhv;
	nd->pgno=pgno;
	nd->haf=(flag&CN_FMASK)|(hv2&CN_HMASK);
	//printf("%s:pgno=%d haf=%x\n",__func__,pgno,nd->haf);
	nd->left=NULL;
	nd->right=NULL;
	while(n!=NULL){
	    nhv=n->haf&CN_HMASK;
	    if(nhv==hv2){
		    if(n->pgno>pgno){
			    pn=n;
			    n=n->left;
			}
			else if(n->pgno<pgno){
			    pn=n;
				n=n->right;
			}else{
		        printf("error:same pageno %d encountered! Will be substituted\n",pgno);getchar();
			    nd->left=n->left;
			    nd->right=n->right;
			    if(pn->pgno>pgno)
	                pn->left=nd;
	            else
			        pn->right=nd;
			    if(cc->first!=NULL)
		            HEADINSERT(cc->first,nd);
	            else{
		            cc->first=cc->last=nd;
	                nd->pre=nd->next=NULL;
	            }
			    n->left=n->right=NULL;
			    if(cc->flast!=NULL){
			        TAILINSERT(cc->flast,n);
			    }
			    else{
			        cc->flast=cc->ffirst=n;
				    n->pre=n->next=NULL;
			    }
			    n->haf=F_FREE|F_DELETE;
			    return true;
			}
		}else{
		    pn=n;
	        if(nhv>hv2) n=n->left;
		    else n=n->right;
		}
	}
	if(pn==NULL)
	    cc->buckets[hv1]=nd;
	else if((uint16)(pn->haf&CN_HMASK)>hv2||(((uint16)(pn->haf&CN_HMASK)==hv2)&&pn->pgno>nd->pgno))
	    pn->left=nd;
	else if((uint16)(pn->haf&CN_HMASK)<hv2||(((uint16)(pn->haf&CN_HMASK)==hv2)&&pn->pgno<nd->pgno))
	    pn->right=nd;
	/*
	if(pn!=NULL){
	    printf("%s:parent pgno=%d flag=%x\n",__func__,pn->pgno,pn->haf);
	    if(pn->left) printf("%s:left pgno=%d flag=%x\n",__func__,pn->left->pgno,pn->left->haf);
	    if(pn->right) printf("%s:right pgno=%d flag=%x\n",__func__,pn->right->pgno,pn->right->haf);
	}
	else printf("%s:add to root flag=%x\n",__func__,nd->haf);*/
	if(cc->first!=NULL)
		HEADINSERT(cc->first,nd);
	else{
		cc->first=nd;
		cc->last=nd;
	    nd->pre=NULL;
		nd->next=NULL;
	}
	/*
	int i;
	for(i=0;i<cc->nbucket;i++){
	    printf("%s:bucket %d\n",__func__,i);
		traverse(cc,i);
	}*/
	return true;
}
int delpage(struct cache *cc,char *p){
    struct cnode *nd=(struct cnode*)(p-sizeof(struct cnode));
	uint32 hv1=hash1((uchar*)&nd->pgno,sizeof(uint64));
	pthread_rwlock_wrlock(&cc->lock);
	if(nd->pre!=NULL)
		nd->pre->next=nd->next;
	else
		cc->first=nd->next;
	if(nd->next!=NULL)
		nd->next->pre=nd->pre;
	else cc->last=nd->pre;
	DEBUG(printf("%s:del pgno=%d\n",__func__,nd->pgno));
	cremove(cc,nd,hv1);
	if(cc->npg>cc->maxpgs){
		free(nd);
		cc->npg--;
	}else{
		if(cc->ffirst!=NULL)
		    HEADINSERT(cc->ffirst,nd);
	    else{
			cc->ffirst=nd;
		    cc->flast=nd;
			nd->next=nd->pre=NULL;
		}
		nd->haf=F_FREE|F_DELETE;
	}
	pthread_rwlock_unlock(&cc->lock);
	return true;
}
int check(struct cache *cc){
    struct cnode *t=cc->last;
	char stop=0;
	while(t!=NULL){
	    if((t->haf&F_READ)||(t->haf&F_WRITE)){
		    printf("%s:pgno=%d flag=%x\n",__func__,t->pgno,t->haf);
			stop=1;break;
		}
		t=t->pre;
	}
	if(stop) getchar();
	return true;
}
int cachedel(struct cache *cc){
    struct cnode *nd=cc->last;
	struct cnode *tnd;
	while(nd!=NULL){
	    if(nd->haf&F_DIRTY){
		    if(seekwrite(cc->fd,(char*)nd+sizeof(struct cnode),cc->pgsiz,nd->pgno)!=cc->pgsiz)
			    printf("%s:write error\n",__func__);
		}
		tnd=nd;
		nd=nd->pre;
		free(tnd);
	}
	free(cc->buckets);
	return true;
}
int cachesyn(struct cache *cc){
    struct cnode *nd=cc->first;
	struct cnode *tmp;
    while(nd!=NULL){
        if(nd->haf&F_DIRTY){
			seekwrite(cc->fd,(char*)nd+sizeof(struct cnode),cc->pgsiz,nd->pgno);
	    }
		tmp=nd->next;
		if(cc->npg>cc->maxpgs){
		    uint32 hv1=hash1((uchar*)&nd->pgno,sizeof(uint64));
		    cremove(cc,nd,hv1);
			free(nd);
			nd=tmp;
			cc->npg--;
			continue;
		}
		nd->haf&=CN_HMASK;
		if(cc->ffirst==NULL){
		    cc->ffirst=cc->flast=nd;
			nd->pre=nd->next=NULL;
		}else{
		    HEADINSERT(cc->ffirst,nd);
		}
		nd=tmp;
    }
	cc->first=cc->flast=NULL;
	return true;
}
void* removenode(struct cache *cc,char *p){
    struct cnode *nd=(struct cnode*)(p-sizeof(struct cnode));
	uint32 hv1=hash1((uchar*)&nd->pgno,sizeof(uint64));
	if(!(nd->haf&F_FREE)){
	    if(nd->pre!=NULL)
		    nd->pre->next=nd->next;
	    else
		    cc->first=nd->next;
	    if(nd->next!=NULL)
		    nd->next->pre=nd->pre;
	    else cc->last=nd->pre;
	}
	nd->haf&=~F_READ&~F_WRITE;
	DEBUG(printf("%s:remove pgno=%d\n",__func__,nd->pgno));
	cremove(cc,nd,hv1);
	cc->npg--;
	return nd;
}
int insertnode(struct cache *cc,void *in,uint32 flag){
    struct cnode *nd=in;
	uint32 hv1=hash1((uchar*)&nd->pgno,sizeof(uint64));
    uint16 hv2=HASH2(hv1);
	nd->haf=flag|(hv2&CN_HMASK);
    hv1=hv1%cc->nbucket;
	//printf("%s:insert node:pgno=%d npg=%d hv1=%d hv2=%d\n",__func__,nd->pgno,cc->npg,hv1,hv2);
	struct cnode *pn=cc->buckets[hv1];
	struct cnode *n=pn;
	uint16 nhv;
    nd->left=NULL;
	nd->right=NULL;
	while(n!=NULL){
	    nhv=n->haf&CN_HMASK;
	    if(nhv==hv2){
		    if(n->pgno>nd->pgno){
			    pn=n;
			    n=n->left;
			}
			else if(n->pgno<nd->pgno){
			    pn=n;
				n=n->right;
			}else{
		        printf("error:same pageno %d encountered! Will be substituted\n",nd->pgno);getchar();
			    nd->left=n->left;
			    nd->right=n->right;
			    if(pn->pgno>nd->pgno)
	                pn->left=nd;
	            else
			        pn->right=nd;
			    if(cc->first!=NULL)
		            HEADINSERT(cc->first,nd);
	            else{
		            cc->first=cc->last=nd;
	                nd->pre=nd->next=NULL;
	            }
			    n->left=n->right=NULL;
			    if(cc->flast!=NULL){
			        TAILINSERT(cc->flast,n);
			    }
			    else{
			        cc->flast=cc->ffirst=n;
				    n->pre=n->next=NULL;
			    }
			    n->haf=F_FREE|F_DELETE;
			    return true;
			}
		}
		pn=n;
	    if(nhv>hv2) n=n->left;
		else n=n->right;
	}
	if(pn==NULL){
	    cc->buckets[hv1]=nd;
		//printf("%s:buckets[%d]=%x\n",__func__,hv1,cc->buckets[hv1]);
	}
	else if((uint16)(pn->haf&CN_HMASK)>hv2||(((uint16)(pn->haf&CN_HMASK)==hv2)&&pn->pgno>nd->pgno))
	    pn->left=nd;
	else if((uint16)(pn->haf&CN_HMASK)<hv2||(((uint16)(pn->haf&CN_HMASK)==hv2)&&pn->pgno<nd->pgno))
	    pn->right=nd;
	if(cc->first!=NULL)
		HEADINSERT(cc->first,nd);
	else{
		cc->first=nd;
		cc->last=nd;
	    nd->pre=NULL;
		nd->next=NULL;
	}
	
	cc->npg++;
	return true;
}
int cacheabort(struct cache *cc){
    struct cnode *nd=cc->first;
	struct cnode *tmp;
    while(nd!=NULL){
		tmp=nd->next;
		if(cc->npg>cc->maxpgs){
		    free(nd);
			cc->npg--;
			nd=tmp;
			continue;
		}
		if(cc->ffirst==NULL){
		    cc->ffirst=cc->flast=nd;
			nd->pre=nd->next=NULL;
		}else{
		    HEADINSERT(cc->ffirst,nd);
		}
		nd->haf=0;
		nd=tmp;
    }
	cc->first=cc->flast=NULL;
	int i;
	for(i=0;i<cc->nbucket;i++){
	    cc->buckets[i]=NULL;
	}
	return true;
}
/*
int main(){
   int fd=open("test.txt",O_RDWR|O_CREAT|O_TRUNC,0640);
   struct cache *cc=cachenew(fd,0,512,5*512,4);
   char page[512];
   memset(page,'a',sizeof(page));
   int i;
#define NUM 10
   char *ps[NUM];
   srand(1);
   int flag=0;
   for(i=0;i<NUM;i++){
       ps[i]=addpage(cc,i*cc->pgsiz,page,F_DIRTY);
   }
   char *p=getpage(cc,1*cc->pgsiz,F_READ);
   putpage(cc,p,0);
   printf("swap times=%d swap num=%d\n",cc->swaptimes,cc->swapnum);
   cachedel(cc);
   close(fd);
}
*/
